package com.lwg.datastructure.CommonSelectMethod;

import java.util.Arrays;

/**
 * @author: lwg
 * @Date: 2022/4/24 17:08
 * @Description: 斐波那契查找
 * 利用斐波那契数组的值得到mid的位置，从而到要查找的数组中去查找key
 * 只要顺序表的长度为 F[k]-1就可以分割为前半部分F[k-1]-1]个元素，后半部分 F[k-2]-1 个元素，
 * 从而确定中间位置为 mid = low+F(k-1)-1，找出要查找的元素在那一部分并递归，直到找到
 * <p>
 * <p>
 * 另一种写法，不用扩充数组
 * 即如果查找的mid 大于数组的长度，则直接让与key比较的值为最后一个值即可
 * 不大于数组的长度，则按正常的赋值即可。即midValue=arr[mid]
 */
public class FbnSearch {
    
    public static int maxSize = 20;
    
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println("index = " + fibSearch(arr, 89));
    }
    
    // 构建斐波那契数列，为了查找得到mid
    public static int[] fb() {
        int[] fb = new int[maxSize];
        fb[0] = 1;
        fb[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            fb[i] = fb[i - 1] + fb[i - 2];
        }
        return fb;
    }
    
    private static int fibSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        
        // 对应斐波那契中的索引下标
        int k = 0;
        int[] fb = fb();
        // 需要保证查找数组中的最大个数小于等于斐波那契中的数，保证查找数组的长度曼度斐波那契的形式
        // 例如该查找数组长度为6 斐波那契数组为 1 1 2 3 5 8 13 21，此时要满足6 <= fb[k] - 1 ，此时k=5
        while (high > fb[k] - 1) {
            k++;
        }
        // 如果要补充元素，则补充重复最后一个元素，直到满足fb[k]个元素 ，防止下方mid =low+fb[k]-1 超出索引，因为low是从0开始的
        // 如果是fb[k-1] 则数组的长度为7，之后计算mid=7，即第八个数字，则超出索引
        // 如果写成fb[k]-1 则mid=int mid = low + fb[k-1] - 1; 直接算出前半部分所含有的中间值
        int[] temp = Arrays.copyOf(arr, fb[k] - 1);
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        
        while (low <= high) {
            int mid = low + fb[k - 1] - 1;
            if (key < temp[mid]) {
                // 前半部分查找
                high = mid - 1;
                //为什么是k--
                //1.全部元素= 前面的元素 + 后边元素
                //2. f[k] = f[k-1] + f[k-2]
                //之前(F[k]-1) = (F[k-1]-1) + (F[k-2]-1) +1
                //按图所示，目前我们这里是mid= low + f[k - 1] -1;
                //如果继续向数组的前面查找(左边)则应该是(F[k-1]-1)进行拆分
                //(F[k-1]-1)=(F[k-1-1]-1) + (F[k-2-2]-1) +1 = 4 = 2 + 1 + 1
                //即在f[k-1]-1 的前面继续查找k--
                //即下次循环mid = f[k-1-1] -1
                k--;
            }
            if (key > temp[mid]) {
                low = mid + 1;
                //为什么是k -=2
                //1. f[k] = f[k-1] + f[k-2] .
                //2.因为后面我们有f[k-2],所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
                //3.即在f[k-2]的前面进行查找k -=2，即下次循环mid = f[k -1 - 2] -1
                k -= 2;
            }
            if (key == temp[mid]) {
                //因为之前如果要补充元素，则补充重复最后一个元素，直到满足F[k]-1个元素
                //如果小于hight代表是arr数组里的值
                if (mid <= high) {
                    return mid;
                } else {
                    //否则说明查找得到的数据元素是temp数组里的补充值
                    return high;
                }
            }
        }
        
        return -1;
    }
    
}
